public class Shell {
    public static void sort(Comparable[] a){
        // 希尔排序
        int n = a.length;
        int h = 1;
        while(h < n/3){
            h = 3*h + 1;
        } // 动态定义间隔h, 定义方式也可以自己实现
        while(h >=1){
            for (int i = h; i < n; i++){
                // 将间隔为h的序列按插入排序算法排序
                Comparable temp = a[i];
                int j = i;
                while(j >= h && less(temp, a[j-h])){
                    a[j] = a[j-h];
                    j-=h;
                }
                a[j] = temp;
            }
            h = h / 3;
        }
    }

    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
}
